package com.itheima.algorithm.queue;

import java.util.Iterator;

/**
 * @author: TylerZhong
 * @description:
 *  E: 队列中元素类型
 */
public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {

    public E[] array;
    public int head;
    public int tail;

    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        /*if ((capacity & capacity - 1) != 0) {
            throw new IllegalArgumentException("capacity 必须是2的幂");
        }*/

        // 2. 改成 2^n 13-> 16  22->32  32->32
        capacity-=1;
        capacity|=capacity>>1;
        capacity|=capacity>>4;
        capacity|=capacity>>8;
        capacity|=capacity>>16;
        capacity+=1;

        array = (E[]) new Object[capacity];
    }

    /**
     * head = 0
     * tail = 3 % 3 = 0
     * capacity = 3
     * @param value - 待插入值
     * @return
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
//        array[tail % array.length] = value;
//        array[(int) (Integer.toUnsignedLong(tail) % array.length)] = value;
        array[tail & (array.length-1)] = value;
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
//        E value = this.array[head % array.length];
//        E value = this.array[(int) (Integer.toUnsignedLong(head) % array.length)];
        E value = this.array[head & array.length - 1];
        head++;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head & array.length -1];
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public boolean isFull() {
        return tail - head == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p & array.length - 1];
                p++;
                return value;
            }
        };
    }

    public static void main(String[] args) {
        int capacity = 13;
        int n = (int)(Math.log10(capacity) / Math.log10(2)) + 1;
        System.out.println(n);
        System.out.println(1<<n);

 /*       int capacity = 29;
        capacity-=1;
        capacity|=capacity>>1;
        capacity|=capacity>>4;
        capacity|=capacity>>8;
        capacity|=capacity>>16;
        capacity+=1;
        System.out.println(capacity);*/
    }
}
